package leetcode.One_hundred_to_Two_hundred;

/**
 * 101. 对称二叉树
 */
public class Test101 {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public boolean isSymmetric(TreeNode root) {
        // null 树也是对称的
        if (root == null) {
            return true;
        }
        // 分左右两边开始递归
        return isSymmetric2(root.left, root.right);
    }

    boolean isSymmetric2(TreeNode left, TreeNode right) {
        // 对称的两边允许同时为 null
        if (left == null && right == null) {
            return true;
        }
        // 不可以存在有一边为 null
        if ((left == null && right != null) || (left != null && right == null)) {
            return false;
        }
        // 符合对称条件的节点继续往下遍历
        if (left.val == right.val) {
            return isSymmetric2(left.left, right.right)
                    && isSymmetric2(left.right, right.left);
        }
        // 以上都不满足，返回 false
        return false;
    }
}
